﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Xml;

using SimpleIR;
using System.Diagnostics.Contracts;

namespace PInfoModel
{
	/// <summary>
	/// Represents a memory location that can have a reference to it taken, so Heap locations and Local stack Locations.
	/// Note we break value types out into their own nodes to that nesting is explicit rather than implicit.
	/// </summary>
	public sealed class PIMNode
	{
		public static readonly PIUseMod[] EmptyUseMod = new PIUseMod[0];
		public static readonly int[] EmptyIdentities = new int[0];
		public static readonly PIEscapeSite[] EmptyEscapes = new PIEscapeSite[0];
		public static readonly PIExternalRef[] EmptyExtRefs = new PIExternalRef[0];
		public static readonly List<PIMEdge> EmptyEdges = new List<PIMEdge>();

		/// <summary>
		/// A unique identifier for a node (within a single graph).
		/// </summary>
		public readonly int LocationAddress;

		/// <summary>
		/// The set of types stored in this location (for fixed root types this may also be pointer and primitive types).
		/// </summary>
		public readonly IRType LocationType;

		/// <summary>
		/// If this node represents the home location for a variable this is the name of that var (null otherwise).
		/// </summary>
		public readonly IRRootIdentifier HomeLocFor;

		/// <summary>
		/// Use/Mod information.
		/// </summary>
		public readonly PIUseMod[] UseModInfo;

		/// <summary>
		/// Track object Identities.
		/// </summary>
		public readonly int[] Identities;

		/// <summary>
		/// True if we know this location represents a single object or struct.
		/// </summary>
		public readonly bool IsUniqueLocation;

		/// <summary>
		/// The orig line this appeared in this method (i.e. the alloc line or the line it escaped at).
		/// Not valid for fixed locations.
		/// </summary>
		public readonly PIEscapeSite[] EscapeLines;

		/// <summary>
		/// List of all the out edges from this node.
		/// </summary>
		public List<PIMEdge> OutEdges;

		/// <summary>
		/// List of all the incomming edges to this node.
		/// </summary>
		public readonly List<PIMEdge> InEdges;

		/// <summary>
		/// Set of all external refs that may refer to this node.
		/// </summary>
		public readonly PIExternalRef[] ExtRefInto;

		/// <summary>
		/// True if this region represents containers which MUST be empty.
		/// </summary>
		public readonly bool ContainerMustBeEmpty;

		[ContractInvariantMethod]
		private void ObjectInvariant()
		{
			Contract.Invariant(this.LocationType != null);
			Contract.Invariant(this.UseModInfo != null);
			Contract.Invariant(this.Identities != null);
			Contract.Invariant(this.OutEdges != null);
			Contract.Invariant(this.InEdges != null);
			Contract.Invariant(this.ExtRefInto != null);

			Contract.Invariant((this.Identities.Length != 0) | this.MayBeInternalAlloc());

			Contract.Invariant((this.UseModInfo.Length != 0) | (this.UseModInfo == EmptyUseMod));
			Contract.Invariant((this.Identities.Length != 0) | (this.Identities == EmptyIdentities));
			Contract.Invariant((this.EscapeLines.Length != 0) | (this.EscapeLines == EmptyEscapes));
			Contract.Invariant((this.ExtRefInto.Length != 0) | (this.ExtRefInto == EmptyExtRefs));

			Contract.Invariant(EmptyEdges.Count == 0);
			Contract.Invariant((this.OutEdges.Count != 0) | (this.OutEdges == EmptyEdges));
		}

		////////////////////////////////
		//Basic Operations

		/// <summary>
		/// Private constructor, takes all of the needed paramters and TAKES ownership of them, assumes all needed sorting has been done.
		/// </summary>
		public PIMNode(int addr, IRType ltype, IRRootIdentifier opthloc, PIUseMod[] umv, int[] identity, bool isunique, PIEscapeSite[] esclocinfo, List<PIMEdge> outedges, List<PIMEdge> inedges, PIExternalRef[] extrefs, bool cmustempty)
		{
			Contract.Requires((umv.Length != 0) | (umv == EmptyUseMod));
			Contract.Requires((identity.Length != 0) | (identity == EmptyIdentities));
			Contract.Requires((esclocinfo.Length != 0) | (esclocinfo == EmptyEscapes));
			Contract.Requires((extrefs.Length != 0) | (extrefs == EmptyExtRefs));
			Contract.Requires((outedges.Count != 0) | (outedges == EmptyEdges));

			this.LocationAddress = addr;
			this.LocationType = ltype;
			this.HomeLocFor = opthloc;
			this.UseModInfo = umv;
			this.Identities = identity;
			this.IsUniqueLocation = isunique;
			this.EscapeLines = esclocinfo;
			this.OutEdges = outedges;
			this.InEdges = inedges;
			this.ExtRefInto = extrefs;
			this.ContainerMustBeEmpty = cmustempty;
		}

		public void AddOutEdge(PIMEdge oe)
		{
			if(this.OutEdges == EmptyEdges)
				this.OutEdges = new List<PIMEdge>();

			this.OutEdges.Add(oe);
		}

		//////////////////////////////////////
		//MAY

		/// <summary>
		/// True if the allocation info value indicates the objects/fixed location MAY BE either (1) allocated in the current call scope or (2) has escaped from a callee method.
		/// </summary>
		[Pure]
		internal bool MayBeInternalAlloc()
		{ return this.EscapeLines.Length != 0; }

		/// <summary>
		/// True if the allocation info value indicates the objects/fixed location MAY BE passed in from the external scope.
		/// </summary>
		[Pure]
		internal bool MayBeExternalAlloc()
		{ return this.Identities.Length != 0; }

		//////////////////////////////////////
		//MUST

		/// <summary>
		/// True if the allocation info value indicates the objects MUST BE either (1) allocated in the current call scope or (2) has escaped from a callee method.
		/// </summary>
		[Pure]
		internal bool MustBeInternalAlloc()
		{ return this.Identities.Length == 0; }

		/// <summary>
		/// True if this MUST represent objects or fixed memory locations that came from an external scope.
		/// </summary>
		[Pure]
		internal bool MustBeExternalAlloc()
		{ return this.EscapeLines.Length == 0; }

		public string GetBasicAllocString()
		{
			if(this.EscapeLines.Length == 0)
				return "HE";
			else
			{
				if(this.Identities.Length == 0)
					return "HI";
				else
					return "HIE";
			}
		}

		public string GetAllocLocationStr()
		{
			StringBuilder sb = new StringBuilder();

			if(this.EscapeLines.Length == 0)
				sb.Append("HE");
			else
			{
				sb.Append("@[");
				for(int i = 0; i < this.EscapeLines.Length; ++i)
				{
					if(i != 0)
						sb.Append(", ");
					sb.Append(this.EscapeLines[i].ToString());
				}
				sb.Append("]");

				if(this.Identities.Length == 0)
					sb.Append("HI");
				else
					sb.Append("HIE");
			}

			return sb.ToString();
		}

		public override string ToString()
		{
			StringBuilder sb = new StringBuilder("(" + this.LocationAddress);

			if(this.IsUniqueLocation && this.HomeLocFor == null)
				sb.Append("@UL");

			sb.Append(", type=" + this.LocationType.ToString());

			if(this.HomeLocFor != null)
				sb.Append("HomeLoc=" + this.HomeLocFor.ToString());

			sb.Append(", UM=[");
			for(int i = 0; i < this.UseModInfo.Length; ++i)
			{
				if(i != 0)
					sb.Append(", ");
				sb.Append(this.UseModInfo[i].ToString());
			}
			sb.Append("]");

			sb.Append(", ID=[");
			for(int i = 0; i < this.Identities.Length; ++i)
			{
				if(i != 0)
					sb.Append(", ");
				sb.Append(this.Identities[i]);
			}
			sb.Append("]");

			sb.Append(this.GetAllocLocationStr());

			sb.Append(", in=[");
			for(int i = 0; i < this.InEdges.Count; ++i)
			{
				if(i != 0)
					sb.Append(", ");
				sb.Append(this.InEdges[i].ToString());
			}
			sb.Append("]");

			sb.Append(", out=[");
			for(int i = 0; i < this.OutEdges.Count; ++i)
			{
				if(i != 0)
					sb.Append(", ");
				sb.Append(this.OutEdges[i].ToString());
			}
			sb.Append("]");

			
			sb.Append(", extr=[");
			for(int i = 0; i < this.ExtRefInto.Length; ++i)
			{
				if(i != 0)
					sb.Append(", ");
				sb.Append(this.ExtRefInto[i].ToString());
			}
			sb.Append("]");

			if(this.ContainerMustBeEmpty)
				sb.Append(" Empty");

			sb.Append(")");
			return sb.ToString();
		}

		internal void Serialize(PInfoSerializer sr)
		{
			sr.WriteStartTag("MNode");

			sr.WriteInt("Addr", this.LocationAddress);
			sr.WriteIRType("LType", this.LocationType);
			sr.WriteBool("Unq", this.IsUniqueLocation);
			sr.WriteBool("CEmpty", this.ContainerMustBeEmpty);

			sr.WriteBool("IsHome", this.HomeLocFor != null);
			if(this.HomeLocFor != null)
				sr.WriteIRRoot("OptHome", this.HomeLocFor);

			sr.WriteCollectionStartTag("Exts", this.ExtRefInto.Length);
			for(int i = 0; i < this.ExtRefInto.Length; ++i)
				this.ExtRefInto[i].Serialize(sr);
			sr.WriteCollectionEndTag("Exts");

			sr.WriteCollectionStartTag("Idents", this.Identities.Length);
			for(int i = 0; i < this.Identities.Length; ++i)
			{
				sr.WriteStartTag("IID");
				sr.WriteInt("TID", this.Identities[i]);
				sr.WriteEndTag("IID");
			}
			sr.WriteCollectionEndTag("Idents");

			sr.WriteCollectionStartTag("Escs", this.EscapeLines.Length);
			for(int i = 0; i < this.EscapeLines.Length; ++i)
				this.EscapeLines[i].Serialize(sr);
			sr.WriteEndTag("Escs");

			sr.WriteCollectionStartTag("UMV", this.UseModInfo.Length);
			for(int i = 0; i < this.UseModInfo.Length; ++i)
				this.UseModInfo[i].Serialize(sr);
			sr.WriteCollectionEndTag("UMV");

			sr.WriteCollectionStartTag("InEdges", this.InEdges.Count);
			for(int i = 0; i < this.InEdges.Count; ++i)
				this.InEdges[i].Serialize(sr);
			sr.WriteCollectionEndTag("InEdges");

			sr.WriteCollectionStartTag("OutEdges", this.OutEdges.Count);
			for(int i = 0; i < this.OutEdges.Count; ++i)
				this.OutEdges[i].Serialize(sr);
			sr.WriteCollectionEndTag("OutEdges");

			sr.WriteEndTag("MNode");
		}

		internal static PIMNode Deserialize(PInfoDeSerializer dsr)
		{
			dsr.ReadStartTag("MNode");

			int addr = dsr.ReadInt("Addr");
			IRType ltype = dsr.ReadIRType("LType");
			bool unq = dsr.ReadBool("Unq");
			bool cempty = dsr.ReadBool("CEmpty");

			bool ishome = dsr.ReadBool("IsHome");
			IRRootIdentifier ohome = null;
			if(ishome)
				ohome = dsr.ReadIRRoot("OptHome");

			int extcount = dsr.ReadCollectionStartTag("Exts");
			PIExternalRef[] exts;
			if(extcount == 0)
				exts = EmptyExtRefs;
			else
			{
				exts = new PIExternalRef[extcount];
				for(int i = 0; i < extcount; ++i)
					exts[i] = PIExternalRef.Deserialize(dsr);
			}
			dsr.ReadCollectionEndTag("Exts");

			int idcount = dsr.ReadCollectionStartTag("Idents");
			int[] ids;
			if(idcount == 0)
				ids = EmptyIdentities;
			else
			{
				ids = new int[idcount];
				for(int i = 0; i < idcount; ++i)
				{
					dsr.ReadStartTag("IID");
					ids[i] = dsr.ReadInt("TID");
					dsr.ReadEndTag("IID");
				}
			}
			dsr.ReadCollectionEndTag("Idents");

			int esccount = dsr.ReadCollectionStartTag("Escs");
			PIEscapeSite[] escs;
			if(esccount == 0)
				escs = EmptyEscapes;
			else
			{
				escs = new PIEscapeSite[esccount];
				for(int i = 0; i < esccount; ++i)
					escs[i] = PIEscapeSite.Deserialize(dsr);
			}
			dsr.ReadCollectionEndTag("Escs");

			int umvcount = dsr.ReadCollectionStartTag("UMV");
			PIUseMod[] umv;
			if(umvcount == 0)
				umv = EmptyUseMod;
			else
			{
				umv = new PIUseMod[umvcount];
				for(int i = 0; i < umvcount; ++i)
					umv[i] = PIUseMod.Deserialize(dsr);
			}
			dsr.ReadCollectionEndTag("UMV");

			int incount = dsr.ReadCollectionStartTag("InEdges");
			List<PIMEdge> inedges;
			if(incount == 0)
				inedges = EmptyEdges;
			else
			{
				inedges = new List<PIMEdge>();
				for(int i = 0; i < incount; ++i)
					inedges.Add(PIMEdge.Deserialize(dsr));
			}
			dsr.ReadCollectionEndTag("InEdges");

			int outcount = dsr.ReadCollectionStartTag("OutEdges");
			List<PIMEdge> outedges;
			if(outcount == 0)
				outedges = EmptyEdges;
			else
			{
				outedges = new List<PIMEdge>();
				for(int i = 0; i < outcount; ++i)
					outedges.Add(PIMEdge.Deserialize(dsr));
			}
			dsr.ReadCollectionEndTag("OutEdges");

			dsr.ReadEndTag("MNode");

			return new PIMNode(addr, ltype, ohome, umv, ids, unq, escs, outedges, inedges, exts, cempty);
		}

		/// <summary>
		/// Compute the dgml representation for heap node. <c>line</c> is a specific line number of -1 for any location.
		/// </summary>
		internal void DGMLDumpHeapNode(int line, XmlWriter xmlw)
		{
			xmlw.WriteStartElement("Node");
			xmlw.WriteAttributeString("Id", this.LocationAddress.ToString());

			string ulls = "@ML";
			if(this.IsUniqueLocation && this.HomeLocFor == null)
				ulls = "@UL";

			StringBuilder idsb = new StringBuilder();
			for(int i = 0; i < this.Identities.Length; ++i)
			{
				if(i != 0)
					idsb.Append(" ");
				idsb.Append(this.Identities[i]);
			}

			StringBuilder escsb = new StringBuilder();
			for(int i = 0; i < this.EscapeLines.Length; ++i)
			{
				if(i != 0)
					escsb.Append(" ");
				escsb.Append(this.EscapeLines[i].EscIdentity);
			}

			if(this.HomeLocFor != null)
			{
				if(this.HomeLocFor is IRStaticField)
					xmlw.WriteAttributeString("Background", "Turquoise");
				else
					xmlw.WriteAttributeString("Background", "Gold");

				xmlw.WriteAttributeString("Label", this.HomeLocFor.ToString());
			}
			else
			{
				string allocs = this.GetBasicAllocString();
				string idstr = (this.MayBeExternalAlloc() ? (" i[" + idsb.ToString() + "]") : "");
				string escstr = (this.MayBeInternalAlloc() ? (" e[" + escsb.ToString() + "]") : "");
				string emptystr = (this.ContainerMustBeEmpty ? " Empty" : "");
				xmlw.WriteAttributeString("Label", "$" + this.LocationAddress.ToString() + ulls + " " + this.LocationType.ToString() + " " + allocs + idstr + escstr + emptystr);
			}

			xmlw.WriteAttributeString("Type", this.LocationType.ToString());

			StringBuilder umsb = new StringBuilder();
			bool isused = false;
			bool isvaluemod = false;
			bool isstructmod = false;
			
			umsb.Append("{");
			for(int i = 0; i < this.UseModInfo.Length; ++i)
			{
				PIUseMod pium = this.UseModInfo[i];
				if(line == -1 || pium.Line == line)
				{
					isused |= ((pium.Tag == PIUseMod.Value.UseAsExternal) | (pium.Tag == PIUseMod.Value.UseAsInternal));

					if((pium.Tag == PIUseMod.Value.ModAsExternal) | (pium.Tag == PIUseMod.Value.ModAsInternal))
					{
						if(pium.UMPath.IsEmptyAccessPath)
						{
							isvaluemod |= (this.LocationType is IRNumericType) || (this.LocationType is IREnumType);
							isstructmod |= (this.LocationType is IRPtrType) || (this.LocationType is IRReferenceType);
						}
						else
						{
							isvaluemod |= (pium.UMPath.PathLast.FieldType is IRNumericType) || (pium.UMPath.PathLast.FieldType is IREnumType);
							isstructmod |= (pium.UMPath.PathLast.FieldType is IRPtrType) || (pium.UMPath.PathLast.FieldType is IRReferenceType);
						}
					}
				}

				if(i != 0)
					umsb.Append(",");
				umsb.Append(pium.ToString());
			}
			umsb.Append("}");

			xmlw.WriteAttributeString("UseMod", umsb.ToString());
			xmlw.WriteAttributeString("Use", isused.ToString());
			xmlw.WriteAttributeString("ModValue", isvaluemod.ToString());
			xmlw.WriteAttributeString("ModStruct", isstructmod.ToString());
			
			xmlw.WriteAttributeString("Escape", this.GetAllocLocationStr());
			xmlw.WriteAttributeString("InternalOrig", (this.EscapeLines.Length != 0).ToString());
			
			xmlw.WriteAttributeString("Identities", idsb.ToString());
			xmlw.WriteAttributeString("ExternalOrig", (this.Identities.Length != 0).ToString());

			xmlw.WriteEndElement();
		}
	}
}
